package com.hutu;

import java.util.*;

/**
 * 全排序  n! 这种
 * 回溯法解决
 *
 * @author hutu
 * @date 2020/10/15 10:30 上午
 */
public class Permute {

    public static List<List<Integer>> permute(int[] nums) {
        // 方结果
        List res = new ArrayList<>();
        // 记录路径
        LinkedList tb = new LinkedList<>();
        backTrack(nums,res,tb);
        return res;
    }

    public static void backTrack(int[] nums,List res, LinkedList tb){
        // 递归结束条件
        if(tb.size()==nums.length){
            res.add(new LinkedList<>(tb));
            return;
        }

        for(int i= 0;i<nums.length;i++){
            // 排除走过的路径
            if(tb.contains(nums[i])){
                continue;
            }
            tb.add(nums[i]);
            backTrack(nums,res,tb);
            tb.removeLast();
        }
    }
    public static void main(String[] args) {
        List<List<Integer>> list = permute(new int[]{1, 2, 3});
        System.out.println();
    }
}
